Image compression is widely used in color raster image processing systems such as those found in printers. Image compression is used in these systems to reduce the amount of memory required to store raster images in the stages between pixel generation and the time when the final output has been delivered from the printer. Reducing the amount of memory reduces the total system cost.
In color printing environments the total uncompressed size of generated pixel images is often large and it is advantageous to avoid storing the entire image. Such pixel images are typically generated in raster or band order. In particular, pixels, scanlines, groups of scanlines, or tiles, are emitted in a stream from a raster image processor (RIP) that has as input an object graphic description of the page to be printed. In some simple cases this raster image data stream may be fed directly to a print engine. However in many circumstances this is not possible. This may be because the print engine requires real-time data delivery, because the image must be kept in case error recovery is required, or because the image must be kept for printing later in a duplexing system. Many other reasons exist. In systems where the raster image data must be kept, the image data is often fed to a compressor in a pipeline fashion such that intermediate storage between the RIP and the compressor is small compared with the total uncompressed image size. The output of the compressor is also considerably smaller than the uncompressed image size.
Many compression schemes can be used in this environment. One widely used method for color images is the baseline method of the Joint Photographic Experts Group (JPEG) standard. However compression using baseline JPEG standard and other methods suffers a number of serious flaws that makes use of such methods difficult in systems with limited memory resources. Existing compression schemes all exhibit one or more of the following flaws when presented with streamed input data:
The memory available to receive the compression data can be over-run. Compression schemes are typically highly data-dependent and without knowing details of the input data ahead of time it is not possible to predict what size output buffer will be required to accept the compressed data. This is a serious problem for systems with limited memory resources. Allocating a large output buffer is typically wasteful, and often still not a guarantee that the compressed data will fit. Some schemes exist that limit total compressed size by maintaining a sufficiently high compression factor on local regions of the image, but in these schemes it is not possible to trade off one part of the image that compresses well against another that does not.
For lossy compression schemes (such as baseline JPEG) the degree of loss must be selected ahead of time. Control of the degree of perceptual degradation (in short, loss) is a common method of controlling the output compression size. But this must generally be selected consistently across a whole image to achieve consistent visual quality, and must be selected at the start of the compression operation.
The image may become unnecessarily compressed. Where a high-loss setting is used for a compression operation, it may transpire that the image data compressed well and a less-lossy setting could have been used in comparison with the system's available memory. A less-lossy setting would have resulted in higher final image quality, which is advantageous.
The compression scheme may require random access to, or multiple passes over, the uncompressed image data. Some compression schemes exist that overcome one or more of the earlier problems by using either random access to the uncompressed image data or by performing multiple passes over it. But this is disadvantageous because it requires storage either of the uncompressed image data or of the original data that is used to generate the image data.
United States Patent Application Publication No. 20020131084 discloses an image processing apparatus for one-pass compression into a fixed size buffer. This system comprises a DCT unit for transforming blocks of pixels into respective blocks of transform coefficients, and a plurality of entropy encoders for encoding respective partitions of the DCT blocks where at least one partition comprises bit-plane data from each of the blocks of transform coefficients. The system also comprises a scan output manager for storing the entropy encoded partitions in a buffer of fixed memory size. The manager manages the storing of the coded partitions in the buffer whereby during the storing of the coded partitions if it is determined the buffer is full, a coded least perceptually significant partition currently stored in the buffer is overwritten by data from a coded more perceptually significant partition.
The aforementioned and other existing image compression schemes execute a series of steps or operations on the original input image data, in order to generate compressed image data. One step typical of most compression schemes is a transformation operation (for example, the Discrete Cosine Transform for JPEG compression), transforming a number of the original image pixels to produce a number of transform coefficients. Another step is an entropy encoding operation, whereby code words are assigned to the transformed coefficients. Both these steps execute, on average, many computations per pixel of the original image, and are critical to the efficiency of the overall compression algorithm.
A difficult image to compress is one whose uncompressed size to compressed size ratio is small. Difficult images present the greatest computational and bandwidth overheads when compressed into, and without overflowing, a fixed size buffer. The image processing apparatus disclosed in the aforementioned United States Patent Application has the disadvantage that it may execute extra, costly computations or require excessive bandwidth in order to avoid overflowing the fixed size buffer when compressing these difficult images.
These problems may also occur in many other related raster image processing systems such as digital cameras and scanners.